Network owners and operators would like to be able to make customers accountable for any problems they cause to their network. One of the biggest problems for most networks is path congestion. When a network is congested then it is not able to provide good service to any of the customers of that network and thus its reputation may suffer. Accountability is generally done on the basis of the volume of traffic passed into the network by a given customer. The present inventors have recognised a need for a more sophisticated mechanism by which network path characteristics such as level of congestion can be collected and used for more accurate accountability purposes. These same characteristics may also be used to give advance notice of potential problems in the network and may be used to enable the network (or an entity operating the network) to react to the problems before they become too severe.
We start by presenting some basic concepts to facilitate the understanding of the mechanisms that are presented later.
Packets
Data networks usually split the data they carry into small units known as packets. The actual communication between endpoints is controlled by various communication protocols. Each communication protocol required to carry the data across the Internet adds a header that contains the required information to enable the data exchange between the end hosts (usually a source host and a destination host). In the internet, one of the most common types of packet consists of a payload that contains the data generated by an application running at the source, encapsulated by a Transmission Control Protocol (TCP) header which ensures the reliable delivery of the data, encapsulated again by an Internet Protocol (IP) header, which ensures that the data reaches the destination host for which it is aimed. The TCP header includes a unique sequence number (to allow the data to be reconstructed at the destination) and the IP header includes the IP addresses of the source and destination host.
Distributed Bandwidth Sharing and Congestion
Data traversing the Internet will follow a path between a series of routers, controlled by various routing protocols. If many paths need to use the same router in the network, this router can get congested (packets experience delays whilst using that network path). If sources persisted sending traffic through that router it may become overloaded or even fail. If sources still persist in sending traffic around this bottleneck it could force more routers to fail, and if the phenomenon keeps spreading, that can lead to a congestion collapse for the whole Internet which occurred regularly in the mid-eighties.
The solution to that problem has been to ensure that sources take responsibility for the rate at which they send over the Internet by implementing congestion control mechanisms. Sources monitor path characterisation metrics to detect when the path their data is following is getting congested, in which case they react by reducing their throughput—while they usually slowly increase it when there is no sign of the path getting congested.
The typical path characterisation metrics sources monitor are the average roundtrip time (RTT) for the data path, the variance of the roundtrip time (jitter), and the level of congestion on the path, which is the primary parameter influencing the data-rate adaptation of a source sending data over a congested path.
The congestion level can be signalled either implicitly (through congested routers dropping packet) or explicitly (through mechanisms such as explicit congestion notification—see next subsection). Currently the most common option has been implicit signalling. Historically, routers would drop packets when they got completely saturated (which happens when a traffic burst cannot be accommodated in the buffer of the router)—this policy is called Droptail. The problem with this is that it can lead to a phenomenon known as global synchronisation which reduces the overall efficiency of the network. An improvement has been proposed where routers monitor the average queue length in their buffer and when the average queue is higher than a given threshold, the router starts to drop packets with a probability which increases with the excess length of the queue over the threshold—this policy is called Random Early Detection (RED). This is discussed in more detail in the document referred to as [RED] in the list of references at the end of this section). It is widely used in today's internet because it allows sources to react more promptly to incipient congestion. Sources using TCP are able to detect losses, because a packet loss causes a gap in the sequence; whenever a source detects a loss, it halves its data-rate, which alleviates the congestion on the router at the bottleneck.
Explicit Congestion Notification
Explicit Congestion Notification (ECN) (discussed in more detail in the document referred to as [ECN]) further improves on RED by using a two-bit ECN field in the IP header to signal congestion. It runs the same algorithm as RED, but instead of dropping a packet, it sets its ECN field to the Congestion Experienced (CE) codepoint. The ECN standard requires the sender to echo any congestion mark signalled in the data; for instance, a TCP receiver sets the Echo Congestion Experienced (ECE) flag in the TCP header, which the TCP source interprets as if the packet has been dropped for the purpose of its rate control. In turn the source reduces its data-rate and sets Congestion Window Reduced (CWR) in the TCP header of the next packet.
The four values of the two-bit ECN field are:                “Not-ECT” (i.e. “Not ECN Capable Transport”), which signifies that the packet belongs to a flow that doesn't support ECN.        “ECT(0)” and “ECT(1)”, which signify that the packet belongs to a flow that supports ECN but and that upstream routers haven't had to mark the packet.        “CE” (i.e. “Congestion Experienced”), which signals to the receiver that a packet has experienced congestion along its path.        
re-Feedback
The re-Feedback proposal [Briscoe05c] provides a mechanism whereby the congestion information that the receiver sends back to the source can be re-inserted into the forward data path, thus allowing nodes along the path to see the downstream congestion information as well as the upstream information. This allows the network provider to trace the source of any congestion and hold the appropriate customer to account for this congestion. Re-ECN is a re-feedback protocol based on ECN which makes use of an additional (i.e. third) bit in the header in order to allow for more than just the four codepoints available in ECN. We introduce the idea of packets having “colours” as a way of explaining the protocol. Packets of different “colours” are distinguishable from each other (i.e. they are assigned different re-ECN codepoints).                “Grey” packets: equivalent to ECT above—the packets are re-ECN packets.        “Red” packets: equivalent to CE above—the packets are “grey” packets that have subsequently been marked by a router as having experienced congestion.        “Black” packets: A sender sends a number of “black” packets corresponding to the number of “red” packets that have been received by the receiver. In order to do this, the receiver must tell the sender the number of “red” packets it has observed coming from the sender. This is achieved via a back-channel such as “acknowledgements” in TCP, or the RTP Control Protocol (RTCP) in RTP (Real-Time Transport Protocol), for example. This information is called the feedback. One of the principal ideas of re-feedback is that the numbers of “black” and “red” packets balance out, i.e. number of “red” packets minus number of “black” packets equals zero.        “Green” packets: When a sender starts to send packets it does not have any feedback on congestion so a number of “green” packets are sent at the start of a flow. Green packets may also be sent when an application increases its sending rate and anticipates that this will cause extra congestion.        “Red-Black” packets: These are initially “black” packets that have subsequently been marked “red” by a router. They are distinguishable from normal “red” packets (i.e. initially “grey” packets that have subsequently been marked “red”).        
The re-ECN protocol allows senders to be held to account for the congestion that they cause. Three mechanisms are proposed:                “Dropper” at the egress on an internetwork        “Policer” at the ingress of the internetwork        “Border Gateways” between individual networks        
The dropper checks that “black” packets=“red” packets for a flow ensuring that senders are sending the right number of “black” packets
The policer allows a sender to send “black” packets at a particular rate. If they send above this rate, packets could be delayed or dropped. The dropper at the egress ensures that they send the right amount of “black” packets.
Border gateways allow bulk policing of traffic between independent networks.
Summary of Prior Techniques
Congestion signalling has been well documented in many forms: whether it is by using an implicit signal [RED] or an explicit binary signal [ECN].
Re-ECN has been discussed above.
The idea of using proxies within a TCP flow has been known for some time, e.g. Performance Enhancing Proxies [RFC3135]. These break a TCP flow into what is effectively two flows back to back which may be used for performance enhancement in satellite communications.
Co-pending European patent application EP 09 250 737.5 (now published as EP2230803A1) filed by the same applicant as the present application relates to techniques for the provision of path characterisation information relating to a network characteristic such as network congestion to nodes in a data network using data units being forwarded from a source to a destination. Data units each having a destination indication from a source are received at a first proxy node. A second proxy node is identified in the network, to which data units may be forwarded before being forwarded to the intended destination; and a first and at least one subsequent data unit are then forwarded from the first to the second proxy node via one or more intermediate nodes. Conditions are assigned to path characterisation metrics in respect of data units traversing a path across the network from the first to the second proxy node, the initial condition being dependent on information received by the first from the second proxy node. Such techniques effectively involve setting up two proxies then running a re-feedback protocol between them.
International patent application WO 2009/090387 relates to techniques for assigning information Indicative of a network characteristic to one of a plurality of data units traversing a path across a network, the data units having associated therewith values indicative of the network characteristic, the path having at least one portion passing through a lower-capability region and at least one portion passing through a higher-capability region, the lower-capability region being a region in which information indicative of the network characteristic may be represented by values having a first resolution, and the higher-capability region being a region in which information indicative of the network characteristic may be represented by values having a second resolution greater than the first resolution. Such techniques relate to a data unit as it passes into the higher-capability region.
[Karimi] and [Medina] describe schemes for using ECN in protocols other than TCP.